package table;
//包保证类的唯一性
//Description:构造单向链表
//ListNode代表一个节点
class ListNode{
    public int val;//代表数据域
    public ListNode next;//存储的是节点的地址所以类型是ListNode（引用类型） 左边next为next域右边为下一个节点
    ListNode(int val){//构造方法 不需要给next赋值  不知道下一个节点的地址
        this.val = val;
    }
}
public class MyLinkedList {
    public ListNode head;//头节点
    ListNode listNode = new ListNode(1);

    //打印链表
    public void display(){
        ListNode cur = this.head;//cur表示每一个节点的位置 从头节点开始遍历
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;//向后移动一个节点
        }
        System.out.println();
    }
    public void display2(ListNode newHead){//从指定位置开始打印
        ListNode cur = newHead;//cur表示每一个节点的位置 从头节点开始遍历
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;//向后移动一个节点
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //得到单链表的长度
    public int size(){
        int count = 0;//节点个数
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //头插法   一定要注意先绑定后面的再换头节点
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;//先让插入的节点的next指向现在的head头节点
        head = node;//然后更换头节点
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){//第一次尾插一定得判断 否则可能会发生异常
            this.head = node;
        }else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //此时cur为最后一个节点
            cur.next = node;
        }
    }
    //寻找要插入的位置
    public ListNode findIndex(int index){
        ListNode cur = this.head;
        while(index - 1 != 0){//要插入节点的的前一个位置
            cur = cur.next;
            index --;
        }
        return cur;
    }
    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > size()){
            System.out.println("index位置不合法");
            return;
        }
        if(index == 0){//头插
            addFirst(data);
        }
        if(index == size()){//尾插
            addLast(data);
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndex(index);//接收要插入位置的前一个节点
        node.next = cur.next;//先把要插入的节点的next域换为原节点的next域
        cur.next = node;//再把插入前的位置节点的next域改为要插入的节点位置
    }
    //找到要删除节点的前驱
    public ListNode search(int key){
        ListNode cur = this.head;
        while(cur.next != null){//不为最后一个节点
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null) {
            System.out.println("这是一个空链表  不能删除");
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;//删除头节点
            return;
        }
        /*ListNode del = new ListNode(key);
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key) {
                cur.next = del.next;
                return;
            }
        cur.next = null;
    }error*/
        ListNode cur = search(key);//找到前驱
        if(cur == null){
            System.out.println("没有你要删除的节点");
            return;
        }
        cur.next = cur.next.next;//让删除前节点的next域等于删除前的后一个节点
    }
    //删除所有值为key的节点
    public ListNode removeAllKey(int key){
        if(this.head == null){//this 是当前类的引用
            System.out.println("空链表");
            return null;
        }
        ListNode prev = this.head;//第一个节点
        ListNode cur = this.head.next;//第一个节点的下一个节点
        while(cur != null){
            if(cur.val == key){//是要删的节点
                prev.next = cur.next;//删除cur节点
                cur = cur.next;//让cur节点移到下一个节点
            }else{
                prev = cur;//移动prev节点到下一个节点
                cur = cur.next;
            }
        }//最后处理头节点
        if(this.head.val == key){
            this.head = this.head.next;
        }
        return this.head;
    }
    //清除所有节点
    public void clear(){
        //this.head = null; 粗暴
        while(head != null){//温柔
            ListNode cur = this.head.next;
            this.head.next = null;
            this.head = cur;
        }
    }

    public ListNode fan() {
        if (this.head == null) {
            return null;
        }
        ListNode n = null;
        ListNode cur = this.head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = n;
            n = cur;
            cur = curNext;
        }
        return cur;
    }

    public ListNode delete(int val){
        if(this.head == null){
            return null;
        }
        ListNode cur = this.head;
        ListNode newHead = new ListNode(-1);
        ListNode prve = newHead;

        while(cur != null){
            if(cur.val != val){//不是要删的
                prve.next = cur;
                prve = cur;
                cur = cur.next;
            }else{
                cur = cur.next;
                if(cur == null){
                    prve.next = null;
                }

            }
        }
        return  newHead.next;
    }






    //反转(把链表反过来)
    public ListNode reverseList(){//画图做
        if(this.head == null) return null;
        ListNode prev = null;
        ListNode cur = this.head;
        //ListNode curNext = this.head.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;//把头节点的引用置为空
            prev = cur;//让prev成为新的头节点
            cur = curNext;//让cur走到下一个节点
        }
        return prev;//最后的新的头节点
    }
    //寻找中间节点
    public ListNode middleNode(){
        if(this.head == null) return null;
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null){ //必须先判断fast不等于空 不然可能空指针异常

            fast = fast.next.next;//一次走两步
            /*if(fast == null) {
                return slow;
            }*///如果是偶数返回中间第一个
            slow = slow.next;//一次走一步  这个如果是偶数返回中间第二个
        }
        return slow;
    }
    //寻找第K个节点
    public ListNode findKthToTail(int k){
        if(k <= 0) return null;
        if(this.head == null) return null;
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(k - 1 != 0){//找到第k - 1个节点 （要找到倒数第K个节点 需要走K - 1步）
            fast = fast.next;
            if(fast == null){//没有size的时候 可以这样做
                System.out.println("没有这个节点");
                return null;
            }
            k --;
        }
        while(fast.next != null){//然后同时开始向后 可找到倒数第k个节点
            fast = fast.next;
            slow =slow.next;
        }
        return slow;
    }
    /*public ListNode merge(MyLinkedList n1,MyLinkedList n2){
        ListNode head1 = n1.head;
        ListNode head2 = n2.head;
        ListNode newHead = null;
        ListNode tmp = newHead;
        while(head1 != null && head2 != null){
            if(head1.val > head2.val){
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }else{
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }
        }
        if(head1 != null){
            tmp.next = head1;
        }else{
            tmp.next = head2;
        }
        return newHead.next;
    }*/
    //不改变原有顺序 把小于x的放在其前面
    public ListNode partition(int x){
        if(this.head == null) return null;
        ListNode as = null;
        ListNode af = null;
        ListNode bs = null;
        ListNode bf = null;
        ListNode cur = this.head;
        while(cur != null){
            if(x < cur.val){//大的节点放在b里面
                if(bs == null){//第一次
                   bs = cur;
                   bf = cur;
                }
                bf.next = cur;//链接后面的
                bf = bf.next;
            }else{
                if(as == null){//小的放在a里面
                    as = cur;
                    af = cur;
                }
                af.next = cur;
                af = af.next;
            }
            cur = cur.next;
        }
        if(as == null){//如果前面没有节点
            return bs;
        }
        af.next = bs;//拼接两段链表
        if(bs != null){
            bf.next = null;//最后一个节点不一定为尾结点
        }
        return as;
    }
    //删除出现的重复节点
    public ListNode deleteDouplication(){
        if(this.head == null) return null;
        ListNode cur = this.head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){//有无相同节点
                while(cur.next != null && cur.val == cur.next.val){//相同节点很多可以走多次
                    cur = cur.next;
                }
                cur = cur.next;//把最后一个相同节点也删除
            }else{
                tmp.next = cur;//不同的放到新链表里面
                tmp = tmp.next;//然后向后走
                cur = cur.next;
            }
            tmp.next = null;//最后一个节点必须是尾结点 防止最后一个节点也是重复的
        }
        return newHead.next;
    }
    //回文数
    public boolean palindrome(){
        if(this.head == null)return false;
        ListNode fast = this.head;
        ListNode slow = this.head;
        ListNode newHead = this.head;
        //找中间节点
        while(fast != null && fast.next != null){
                fast = fast.next.next;//一次跑两步
                slow = slow.next;//一次跑一步
        }
        ListNode cur = slow.next;//把slow后面的  记住  后面反转
        //反转slow后面的节点
        while(cur != null) {
            ListNode curNext = cur.next;// cur的下一个节点  否则后面改了其next之后不能修改了
            cur.next = slow;//反转
            slow = cur;//把slow放到后面一个节点
            cur = curNext;//直接向后走
        }
        //回文判断 前后对比
        while(newHead != slow ){
            if(newHead.val != slow.val){
                return false;
            }
            if(newHead.next == slow){//偶数的情况
                return true;
            }
            newHead = newHead.next;
            slow = slow.next;
        }
        return true;
    }
    //成环
    public boolean hasCycle(){
        if(this.head == null)return false;
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;//走其他的步数容易错过
            slow =slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }



    public ListNode findCycle(){
        if(this.head == null)return null;
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next ==null)//如果有空就不是环
            return null;
        /**
         * 找到相遇节点 从头节点和相遇节点开始同时走  第一次相遇即为环入口
         * 设 起始点到 入口 距离为x 环大小为z  入口到相遇点的距离为y
         * 则slow到相遇点的距离为 x+ c- y fast路程为x+ Nc（可以走任何圈 N越大 环越小） + c-y
         * fast路程更是slow路程的二倍 由此可得x = （N-1）c +y则可得到上面的结论同时开始走第一次相遇即为入口
         */
        slow = this.head;
        while(fast != slow){//是否相遇
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
